package LeetCode.month03.day82;

import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;

/**
 * @author 16778
 * @date 2025/10/22 8:16
 * @description
 */
public class No433 {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> cnt = new HashSet<>();
        Set<String> visited = new HashSet<>();
        char[] keys = {'A','C','G','T'};
        for (String s : bank) {
            cnt.add(s);
        }
        if(startGene==endGene) return 0;
        if(!cnt.contains(endGene)) return -1;
        int step = 1;
        Queue<String> queue = new ArrayDeque<>();
        queue.offer(startGene);
        visited.add(startGene);
        while(!queue.isEmpty()){
            int n = queue.size();
            for (int x = 0; x < n; x++) {
                String s = queue.poll();
                for (int i = 0; i < 8; i++) {
                    for (int j = 0; j < 4; j++) {
                        if(keys[j]!=s.charAt(i)){
                            StringBuilder sb = new StringBuilder(s);
                            sb.setCharAt(i,keys[j]);
                            String s1 = sb.toString();
                            if(!visited.contains(s1)&&cnt.contains(s1)){
                                if(s1.equals(endGene)) {
                                    return step;
                                }
                                queue.offer(s1);
                                visited.add(s1);
                            }
                        }
                    }
                }
            }
            step++;
        }
        return -1;
    }
}
